import java.util.Stack;

public class Test1 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length(); i++) {
            char tmp = s.charAt(i);
            if (tmp == '(' || tmp == '[' || tmp == '{') {
                stack.push(tmp);
            } else {
                if(tmp == ')' && stack.peek() != '(') {
                    return false;
                }
                if(tmp == ']' && stack.peek() != '[') {
                    return false;
                }
                if(tmp == '}' && stack.peek() != '}') {
                    return false;
                }
            }
            stack.pop();
        }
        return stack.empty();
    }
}